class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size();
        sort(nums1.begin(), nums1.end());
        vector<int> index(n);
        for (int i = 0; i < n; i++) index[i] = i;
        sort(index.begin(), index.end(), [&](int i, int j) {
            return nums2[i] < nums2[j];
            });
        vector<int> ret(n);
        int left = 0, right = n - 1;
        for (auto e : nums1)
        {
            if (e > nums2[index[left]]) ret[index[left++]] = e;
            else ret[index[right--]] = e;
        }
        return ret;
    }
};

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) {
        int m = 0, minmin = INT_MAX, n = nums.size();
        for (auto e : nums)
        {
            if (e < 0) m++;
            minmin = min(minmin, abs(e));
        }
        int ret = 0;
        if (m > k)
        {
            sort(nums.begin(), nums.end());
            for (int i = 0; i < k; i++)
                ret += -nums[i];
            for (int i = k; i < n; i++)
                ret += nums[i];
        }
        else
        {
            for (auto e : nums) ret += abs(e);
            if ((k - m) % 2)
                ret -= minmin * 2;
        }
        return ret;


    }
};
class Solution {
public:
    vector<string> sortPeople(vector<string>& names, vector<int>& heights) {
        int n = names.size();
        vector<int> arr(n);
        for (int i = 0; i < n; i++) arr[i] = i;
        sort(arr.begin(), arr.end(), [&](int i, int j) {
            return heights[i] > heights[j];
            });
        vector<string> ret;
        for (auto e : arr)
            ret.push_back(names[e]);
        return ret;
    }
};
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        return dp[m][n];

    }
};
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& ob) {
        int m = ob.size(), n = ob[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[0][1] = 1;
        for (int i = 1; i <= m; i++)
            for (int j = 1; j <= n; j++)
                if (ob[i - 1][j - 1] == 0)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        return dp[m][n];
    }
};